Packet classification is performed by devices in data processing systems, in particular data communications networks, to determine how data packets should be handled by the processing device. For example, to implement network services such as routing, differentiated QoS (Quality-of-Service), firewall access control, traffic shaping etc., various packet “flows” are defined. A flow is essentially a set of data packets to which a specified handling policy, or “rule”, applies. Such rules may specify, for example, whether a packet should be forwarded or filtered, where it should be forwarded to, the priority or class of service to be applied to the packet, and the amount to be charged for the transmission. The particular flow to which a packet belongs, and hence the processing rule to be applied to the packet, is determined from the values of various data items in the packet, typically some combination of values in the packet header fields such as the source IP (Internet Protocol) address, destination IP address, source and destination port numbers, protocol, etc. By way of example, a rule might specify that all packets from particular source addresses to particular destination addresses should be forwarded with highest priority, or, in a firewall for example, should be denied access. For each data item in the packet format which must be evaluated to determine applicability of a given rule, the rule specifies a corresponding range of data values, referred to herein as a “rule range”, for which the rule applies. In general, a rule range may consist of a single value or a series of (not necessarily contiguous) values for the data item in question, and may be defined in various ways e.g. by the first and last values in a series, or by a prefix, or by an exact value for single-value ranges. In any case, for each rule, a rule range is defined for each of the data items to be evaluated, and a packet is identified as belonging to the flow for which the rule applies if each of the relevant data item values in the packet intersects (i.e. lies within) the corresponding rule range. Where a set of rules is such that a given packet may satisfy the conditions of more than one rule in the set, then the rules can be prioritized on some basis and the highest priority rule satisfied by the data packet selected as the applicable rule for that packet.
The basic process described above is generally referred to as “multi-field” packet classification since evaluation of multiple data items (typically packet header fields) is required as part of the classification process. Combinations of data item values in a packet are effectively mapped to applicable rules via a search process, which may involve a number of stages, with the input data item values providing the initial search keys for the search process. Current multi-field classification schemes can be divided into three categories:
(1) schemes that convert the multi-field search problem into a single-field problem by concatenating the individual data items together to form one large, composite search key which is then searched using a single-field search algorithm;
(2) schemes that search the multiple data items sequentially in a dependent manner, i.e. the results for data items that have already been searched influence the way subsequent data items are searched; and
(3) schemes that search each data item independently and then determine the classification result based on the results of the item searches, e.g. by an additional, final search.
One example of a category scheme is disclosed in our copending European patent application published under EP-A-1128608, and a related scheme is discussed in IBM Research Report RZ 3210, “Prefix-based Parallel Packet Classification, Engbersen et al., published on 3 Jun. 2000. Another example is disclosed in our copending U.S. patent application Ser. No. 10/090,592. Further category systems are disclosed in: Proc. ACM SIGCOMM'98, Comp. Commun. Rev. Vol. 28, No. 4, October 1998, pp. 203-214, “High-Speed Policy-based Packet Forwarding using Efficient Multi-dimensional Range Matching”, Lakshman et al; and ACM SIGCOMM'99, Comp. Commun. Rev. Vol. 29, No. 4, October 1999, pp. 147-160, “Packet Classification on Multiple Fields”, Gupta et al. The latter two systems are summarized in “Dynamic Multi-Field Packet Classification”, van Lunteren et al., Proceedings of the IEEE Global Telecommunications Conference GLOBECOM'02, Taipei Taiwan, November 2002, together with a scheme based on that described in our US patent application referenced above.
All of the referenced category schemes perform independent item searches for each data item to be evaluated in the data packet, i.e. the result of each item search is not dependent on the result of any other. In each case, the item search for a particular data item involves the selection, via some form of search data structure, of an identifier corresponding to the value of that data item from a predetermined set of identifiers. This set of identifiers, referred to herein as “range identifiers”, effectively indicate, for all possible values of the data item, which of the rule ranges corresponding to that data item a value intersects. The particular way in which a range identifier indicates the intersected rule ranges varies from scheme to scheme. For example, in the Lakshman reference above, all rule information (i.e. rule ranges and rule priorities) is encoded in the range identifiers, so that the highest priority applicable rule can be determined directly from the set of range identifiers for a given packet, here by a logical AND operation, without performing a final search. In contrast, in the Gupta reference above, no rule information whatsoever is encoded in the range identifiers. The identifiers here are simply arbitrary values which distinguish the different combinations of intersected rule ranges for possible data item values. These identifiers are linked to applicable rules via the final search structure which contains rule data encoding all the rule information. The range indicators in this scheme thus indicate the intersected rule ranges indirectly via the final search structure. In the other schemes referenced above, the range identifiers are generated by various processes based on the concept of “primitive range hierarchies”. Here some, but not all, of the rule information is encoded in the range identifiers, the remaining rule information being encoded in the rule data contained in the final search structure. In any case, where a final search is employed in these schemes, the rule data used in the final search effectively encodes the rule ranges for each rule in the rule set, in that range identifiers indicating rule ranges intersected by item values are linked via the final search structure to applicable rules.
Multi-field packet classification is typically performed by each data processing device (such as servers, switches, routers, bridges, brouters, etc.) in the path across a network system, be it a network or internetwork, via which the packet is forwarded between its source and destination nodes. Due to the increasing volume of traffic handled by modem network systems, and continuing improvements in network technologies, the fundamental task of packet classification is increasingly critical to overall network efficiency. Advanced packet classifiers that are capable of examining packets at full wire-speed against large and dynamic sets of complex classification rules are essential building blocks for realizing important emerging Internet applications such as QoS, firewalls, and web-server load balancing. While the problem of searching based on single packet fields (e.g. routing table look-ups) is considered to be well solved, multi-field classification remains a challenging problem. This is due to the multi-field nature of the search process as described above, in combination with the large number of bits, often of the order of hundreds, that have to be inspected for each packet. Meeting the wire-speed challenge in a cost-efficient manner requires classifiers that are also highly storage-efficient. This is necessary because SDRAM performance cannot keep pace with rapidly-increasing link speeds, forcing classifiers to use faster memory technologies, such as SRAM, embedded DRAM and ternary CAM (TCAM), which are substantially more expensive and have significantly smaller storage capacity. Adding to the challenge, the dynamic nature of several new applications also necessitates improved update rates to accommodate rule changes, this typically being a conflicting goal.
It will be appreciated from the foregoing discussion of basic multi-field classification processes that improving efficiency of these processes is a highly desirable objective. However, while the discussion has focused on packet classification for a single rule set, it is often necessary to classify data packets according to a plurality of different rule sets, thus compounding the basic problems discussed above. For example, different rule sets may be provided for different processing applications, such as ACL (Access Control List) in firewalls, QoS, etc., of a network device, so that a given packet must be classified according to each of the rule sets to determine the applicable rule in each case. At present, separate multi-field classification processes are performed for each rule set in turn. This introduces additional performance delays as well as exacerbating the fundamental difficulties already discussed.